package heap

//堆排序
/**
	规则：
		 1.把无序数组生成完整二叉树
		 2.把完整二叉树顶节点取出末节点替换顶节点
		 3.整理二叉树重新生成完整二叉树
		 4.重复2操作
**/

//Sort v or int array
func Sort(value []int) {
	length := len(value)               //获取数组的长度
	for i := length / 2; i >= 0; i-- { //生成初始二叉树
		arrangement(i, length, value) //从i为节点整理二叉树
	}

	for i := length - 1; i > 0; i-- { //进行 length - 1 次排序
		value[0], value[i] = value[i], value[0] // 把输出的最大值放到 length - 1
		arrangement(0, i, value)                //筛选最大值到v[0]
	}
}

//num 父节点，size 长度，v二叉树
func arrangement(num, size int, v []int) {
	left := 2*num + 1 //获取左节点

	for size > left { //判断左节点存不存在

		if size > left+1 && v[left+1] > v[left] { // 判断右节点存不存在 如果存在 判断左右那个节点大 输出最大的节点
			left++
		}

		if v[num] > v[left] { //判断父节点和子节点谁大   如果父节点大则退出
			break
		}

		v[num], v[left] = v[left], v[num] // 子节点和父节点互换

		num = left       //把最大的子节点设置成新的父节点
		left = 2*num + 1 // 获取新的左节点
	}

}
